package com.yuren.codecrushlearn.Q5400;

import java.util.*;

/**
 * Created with Intellij IDEA.
 * Description:
 * Dijkstra算法
 * @author 10204
 * @date 2025-06-18 23:20
 */
public class Q5456 {
    private int v;
    private List<List<Pair<Integer, Integer>>> adj;

    public Q5456(List<List<Integer>> edges, int e, int v) {
        this.v = v;
        this.adj = new ArrayList<>();
        for (int i = 0; i < v; i++) {
            adj.add(new ArrayList<>());
        }
        for (List<Integer> edge : edges) {
            addEdge(edge.get(0), edge.get(1), edge.get(2));
        }
    }

    public void addEdge(int v1, int v2, int weight) {
        adj.get(v1).add(new Pair<>(v2, weight));
    }

    public int shortestPathDijkstra(int s, int t) {
        int[] dist = new int[v];
        Arrays.fill(dist, Integer.MAX_VALUE);
        PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(Comparator.comparingInt(Pair::getKey));
        dist[s] = 0;
        pq.offer(new Pair<>(0, s));

        while (!pq.isEmpty()) {
            Pair<Integer, Integer> current = pq.poll();
            int u = current.getValue();
            for (Pair<Integer, Integer> edge : adj.get(u)) {
                int v = edge.getKey();
                int weight = edge.getValue();
                if (dist[v] > dist[u] + weight) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new Pair<>(dist[v], v));
                }
            }
        }
        return dist[t] == Integer.MAX_VALUE ? -1 : dist[t];
    }

    static class Pair<K, V> {
        private K key;
        private V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }
}
